package LeetCode刷题;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @program: Java_Study
 * @author: Xiaofan
 * @createTime: 2021-07-19 15:45
 * @description: Functions of this class is 把一些数字插入到二叉树
 **/
public class 将数组转化成二叉树 {
    private static class Node{
        Integer data;
        Node left,right;
    }
    public static void main(String args[]){
        Scanner scanner=new Scanner(System.in);
        int n=scanner.nextInt();
        int nums[]=new int[n];
        for(int i=0;i<n;i++){
            nums[i]=scanner.nextInt();
        }
        quickSort(nums,0,nums.length-1);
        System.out.println("快速排序后的数组："+ Arrays.toString(nums));
        Node T=createTree(nums,0,nums.length-1);
        System.out.println("树中元素为（中序排列）：");
        inOrder(T);
        System.out.println();
    }
    private static Node createTree(int nums[],int left,int right){
        Node root=null;
        if(left<=right){
            int mid=(left+right)>>1;
            root=new Node();
            root.data=nums[mid];
            root.left=createTree(nums,left,mid-1);
            root.right=createTree(nums,mid+1,right);
        }
        return root;
    }
    public static void inOrder(Node T) {
        if (T != null) {
            inOrder(T.left);
            System.out.print(T.data + " ");
            inOrder(T.right);
        }
    }
    private static void quickSort(int nums[],int left,int right){
        if(left<right){
            int mid=position(nums,left,right);
            quickSort(nums,left,mid-1);
            quickSort(nums,mid+1,right);
        }
    }
    private static int position(int nums[],int left,int right){
        int i=left;
        int j=right;
        int midNum=nums[left];
        while (i<j){
            while (i<j&&nums[j]>midNum){
                j--;
            }
            while (i<j&&nums[i]<=midNum){
                i++;
            }
            if(i<j){
                swap(nums,i++,j--);
            }
        }
        while (nums[i]>midNum){
            i--;
        }
        swap(nums,i,left);
        return i;
    }
    private static void swap(int nums[],int i,int j){
        int temp=nums[i];
        nums[i]=nums[j];
        nums[j]=temp;
    }
}